package com.haidechizi.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: wangdejun
 * @create: 2020-04-08 11:33
 **/
public class _13_机器人的运动范围 {

    int count = 1;

    public int movingCount(int m, int n, int k) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0));
        int[][] nums = new int[m][n];
        nums[0][0] = 1;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int i = node.i;
            int j = node.j;
            add(i, j + 1, queue, nums, m, n, k);
            add(i, j - 1, queue, nums, m, n, k);
            add(i + 1, j, queue, nums, m, n, k);
            add(i - 1, j, queue, nums, m, n, k);

            /*if (nums[i][j + 1] == 0) {
                Node right = new Node(i, j + 1);
                boolean flag = check(right, m, n, k);
                if (flag) {
                    queue.add(right);
                    nums[i][j + 1] = 1;
                    count++;
                }
            }
            if (nums[i][j - 1] == 0) {
                Node left = new Node(i, j - 1);
                boolean flag = check(left, m, n, k);
                if (flag) {
                    queue.add(left);
                    nums[i][j - 1] = 1;
                    count++;
                }
            }
            if (nums[i + 1][j] == 0) {
                Node down = new Node(i + 1, j);
                boolean flag = check(down, m, n, k);
                if (flag) {
                    queue.add(down);
                    nums[i + 1][j] = 1;
                    count++;
                }
            }
            if (nums[i - 1][j] == 0) {
                Node up = new Node(i - 1, j);
                boolean flag = check(up, m, n, k);
                if (flag) {
                    queue.add(up);
                    nums[i - 1][j] = 1;
                    count++;
                }
            }*/
        }
        /*int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                count += nums[i][j];
            }
        }*/
        return count;
    }

    public void add(int i, int j, Queue<Node> queue, int[][] nums, int m, int n, int k) {
        if (i < 0 || i >= m) {
            return;
        }
        if (j < 0 || j >= n) {
            return;
        }

        if (nums[i][j] == 0) {
            Node up = new Node(i, j);
            boolean flag = check(up, m, n, k);
            if (flag) {
                queue.add(up);
                nums[i][j] = 1;
                count++;
            }
        }
    }

    public boolean check(Node node, int m, int n, int k) {
        if (node.i < 0 || node.i >= m) {
            return false;
        }
        if (node.j < 0 || node.j >= n) {
            return false;
        }
        if (sum(node.i, node.j) <= k) {
            return true;
        }
        return false;
    }

    public int sum(int i, int j) {
        int i1 = i / 100;
        int i2 = i / 10 % 10;
        int i3 = i % 10;

        int j1 = j / 100;
        int j2 = j / 10 % 10;
        int j3 = j % 10;

        return i1 + i2 + i3 + j1 + j2 + j3;

    }

    private static class Node {
        int i;
        int j;

        public Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}
